#include<tools/doublerbtree.h>


#define COLOR_BLACK                     0x0ull


#define COLOR_RED                       0x1ull


#ifdef _RB_USE_AUGMENTED_PTR /* Should we augment the pointer with the color metadata */

#define RB_TREE_COLOR_SHIFT                         63 /* TODO: parameterize me */


#define RB_TREE_PARENT_PTR_MASK                     ((1ull << RB_TREE_COLOR_SHIFT) - 1)

#define _RB_TREE_GET_PARENT_COLOR_MASK(__node)      (((size_t)(__node)->parent) & ~RB_TREE_PARENT_PTR_MASK)

#define RB_TREE_NODE_GET_COLOR(_node)               ((((size_t)(_node)->parent) >> RB_TREE_COLOR_SHIFT) & 1)

#define RB_TREE_NODE_SET_COLOR(_node, _color)       do { (_node)->parent = (struct Int_RB_Tree_Node *)((((size_t)(_node)->parent) & RB_TREE_PARENT_PTR_MASK) | ((_color) << RB_TREE_COLOR_SHIFT)); } while (0)


#define RB_TREE_NODE_GET_PARENT(_node)              ((struct Int_RB_Tree_Node *)(((size_t)(_node)->parent) & RB_TREE_PARENT_PTR_MASK))


#define RB_TREE_NODE_SET_PARENT(_node, _parent)     do { (_node)->parent = (struct Int_RB_Tree_Node *)((size_t)(_parent) | _RB_TREE_GET_PARENT_COLOR_MASK((_node))); } while (0)

#else
#define RB_TREE_NODE_GET_COLOR(_node)               ((_node)->color)
#define RB_TREE_NODE_SET_COLOR(_node, _color)       do { ((_node)->color = (_color)); } while (0)
#define RB_TREE_NODE_GET_PARENT(_node)              ((_node)->parent)
#define RB_TREE_NODE_SET_PARENT(_node, _parent)     do { ((_node)->parent = (_parent)); } while (0)

#endif 


static void double_rb_tree_free_one_node(struct Double_RB_Tree*tree,struct Double_RB_Tree_Node*n)
{
    if(n==NULL||tree==NULL)
    {
        return;
    }
    if(n->left!=NULL)
    {
        double_rb_tree_free_one_node(tree,n->left);
    } 
    if(n->right!=NULL)
    {
        double_rb_tree_free_one_node(tree,n->right);
    }
    free(n);
}


void double_rb_tree_free(struct Double_RB_Tree *tree)
{
    if(tree==NULL)
    {
        return ;
    }
    double_rb_tree_free_one_node(tree,tree->root);
    free(tree);
}

static void double_rb_tree_free_one_node_value(struct Double_RB_Tree*tree,struct Double_RB_Tree_Node*n)
{
    if(n==NULL||tree==NULL)
    {
        return;
    }
    if(n->left!=NULL)
    {
        double_rb_tree_free_one_node_value(tree,n->left);
    } 
    if(n->right!=NULL)
    {
        double_rb_tree_free_one_node_value(tree,n->right);
    }
    if (n->data!=NULL){free(n->data);n->data=NULL;}
}
void double_rb_tree_free_value(struct Double_RB_Tree* tree)
{
    if(tree==NULL)
    {
        return ;
    }
    double_rb_tree_free_one_node_value(tree,tree->root);
}